/*插入排序：将整个数组视为一堆扑克牌，每次从牌堆里摸入一张牌然后插入到相应的位置，把所有牌起完，自然就有序了！*/
#include<stdio.h>
int main()
{
	const int SIZE = 9;
	int arr[SIZE] = {3,2,5,8,6,9,4,1,7};
	//总共需要摸多少张牌
	for(int i=0; i<SIZE; i++){	
		int num = arr[i];      //摸上来的牌
		int pos = -1;          //需要插入的位置
		//第1张牌不需要比较
		if(i==0){
			continue;
		}
		//从第2张牌开始，每次摸上来1张牌需要与手上已有所有牌进行比对，从而算出应该插入的位置
		for(int j=0; j<i; j++){
			if(num < arr[j]){
				pos = j;
				break;
			}
		}
		//没有找到对应的位置，则按兵不动
		if(pos==-1){
			continue;
		}
		//从pos位置开始一直到位置i-1，整体后移1位，腾出位置给num，原来处于i-1位置的元素正好覆盖掉位置i
		//这里一定要倒过来遍历，否则前边的元素会覆盖掉后边的元素导致错误！！！
		for(int k=i-1; k>=pos; k--){
			arr[k+1] = arr[k];
		}
		arr[pos] = num;
	}

	//输出排序后的数组
	for(int i=0; i<SIZE; i++){
		printf("%d\t", arr[i]);
	}
	
	return 0;
}
